package cn.demoncat.util.lang.entity.data;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.function.Consumer;

/**
 * 哈希（散列）表
 * 
 * @author 延晓磊
 *
 * @since 2020年7月16日
 */
public class HashTable<K, V> implements Iterable<MapEntry<K, V>> {

	// 数据量
	private int size = 0;
	// 容量（散列数）
	private int capacity = 16;
	// 散列表
	private SingleLinkedList<MapEntry<K, V>>[] table;

	/**
	 * 构建
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public HashTable() {
		super();
		initTable();
	}

	/**
	 * 构建
	 * 
	 * @param capacity 容量（散列数）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public HashTable(int capacity) {
		super();
		this.capacity = capacity;
		initTable();
	}

	/**
	 * 元素数量
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public int size() {
		return this.size;
	}

	/**
	 * 是否为空
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public boolean isEmpty() {
		return this.size == 0;
	}
	
	/**
	 * 查找
	 * 
	 * @param k 键
	 * 
	 * @return 值
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public V get(K k) {
		// 散列地址对应的链表
		SingleLinkedList<MapEntry<K, V>> list = table[hash(k)];
		// 查找数据
		MapEntry<K, V> data = list.search(new MapEntry<>(k));
		return data == null ? null : data.getVal();
	}

	/**
	 * 保存
	 * 
	 * @param k 键，存在则修改
	 * @param v 值
	 * 
	 * @return 原值，未修改返回null
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public V put(K k, V v) {
		// 散列地址对应的链表
		SingleLinkedList<MapEntry<K, V>> list = table[hash(k)];
		// 节点数据
		MapEntry<K, V> data = new MapEntry<>(k, v);
		// 查询链表节点
		LinkedNode<MapEntry<K, V>> node = list.searchNode(data);
		V ov = null;
		if (node == null) {
			// 添加元素
			list.add(data);
			size++;
		} else {
			// 修改元素
			ov = node.getData().getVal();
			node.setData(data);
		}
		return ov;
	}

	/**
	 * 删除
	 * 
	 * @param k 键
	 * 
	 * @return 原值，null表示不存在/值为null
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public V remove(K k) {
		// 散列地址对应的链表
		SingleLinkedList<MapEntry<K, V>> list = table[hash(k)];
		int listSize = list.size();
		// 删除数据
		MapEntry<K, V> data = list.remove(new MapEntry<>(k));
		if (listSize > list.size()) {
			size--;
		}
		return data == null ? null : data.getVal();
	}
	
	/**
	 * 遍历
	 * 
	 * @param action
	 *
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	@Override
	public void forEach(Consumer<? super MapEntry<K, V>> action) {
		if (!isEmpty()) {
			// 遍历数组
			for (SingleLinkedList<MapEntry<K, V>> list : table) {
				// 遍历链表
				list.forEach(action);
			}
		}
	}

	/**
	 * 迭代器（forEach）
	 * 
	 * @return
	 *
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	@Override
	public Iterator<MapEntry<K, V>> iterator() {
		return new Itr();
	}
	
	/**
	 * 获取EntrySet
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public Set<MapEntry<K,V>> entrys(){
		Set<MapEntry<K,V>> set = new HashSet<>(this.size);
		for (MapEntry<K, V> entry : this) {
			set.add(entry);
		}
		return set;
	}
	
	/**
	 * 获取KeySet
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public Set<K> keys(){
		Set<K> set = new HashSet<>(this.size);
		for (MapEntry<K, V> entry : this) {
			set.add(entry.getKey());
		}
		return set;
	}
	
	/**
	 * 获取ValueList
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public List<V> values(){
		List<V> list = new ArrayList<>(this.size);
		for (MapEntry<K, V> entry : this) {
			list.add(entry.getVal());
		}
		return list;
	}
	
	@Override
	public String toString() {
		if (isEmpty()) {
			 return "{}";
		}
		StringBuilder sb = new StringBuilder();
        sb.append('{');
        for (MapEntry<K, V> entry : this) {
			sb.append(entry);
			sb.append(", ");
		}
        sb.delete(sb.length()-2, sb.length());
        sb.append("}");
		return sb.toString();
	}

	/**
	 * 初始化散列表
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	@SuppressWarnings("unchecked")
	private void initTable() {
		// 创建散列表
		this.table = (SingleLinkedList<MapEntry<K, V>>[]) (new SingleLinkedList[this.capacity]);
		// 初始化
		for (int i = 0; i < table.length; i++) {
			table[i] = new SingleLinkedList<>();
		}
	}

	/**
	 * 哈希函数
	 * 
	 * @param key
	 * 
	 * @return 散列地址
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	private int hash(Object key) {
		return (key == null) ? 0 : key.hashCode() % capacity;
	}
	
	/**
	 * 迭代器（forEach）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	private class Itr implements Iterator<MapEntry<K, V>>{
		
		// 读取计数
		private int count = 0;
		// 数组索引
		private int i = 0;
		// 链表元素
		private LinkedNode<MapEntry<K, V>> curr = table[0].first;
		
		@Override
		public boolean hasNext() {
			return count < size;
		}

		@Override
		public MapEntry<K, V> next() {
			// 节点为空
			if (curr == null) {
				// 下一个链表
				i++;
				curr = table[i].first;
				return next();
			}
			// 读取数据
			MapEntry<K, V> data = curr.getData();
			// 下一个
			count++;
			curr = curr.getNext();
			return data;
		}
	}

}
